package a_12届蓝桥真题;

/*
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由2021个结点组成，依次编号1至2021。
对于两个不同的结点a, b,如果a和b的差的绝对值大于21，则两个结点之间没有边相连:
如果a和b的差的绝对值 <= 21,则两个点之间有一条长度为a和b的最小公倍数的无向边相连。

例如:
结点1和结点23之间没有边相连;
结点3和结点24之间有一条无向边，长度为24;
结点15和结点25之间有一条无向边，长度为75。

请计算，结点1和结点2021之间的最短路径长度是多少。
10266837
 */
public class e路径 {
	public static void main(String[] args) {
		e路径 test = new e路径();
		test.useDeal();
	}
	
	public void useDeal() {
		final int NoAccess = Integer.MAX_VALUE;//无法到达；设成最大程度
		int[][] adjacencyMatrix = new int[2048][2048];//声明邻接矩阵；长度只要比2021长就行
		for (int i = 0; i < 2048; i++) {//初始化邻接矩阵；互相之间无法到达
			for (int j = 0; j < 2048; j++) {
				adjacencyMatrix[i][j] = NoAccess;
			}
		}
		int res = deal(adjacencyMatrix, NoAccess);
		System.out.println(res);
	}
	
	public int deal(int[][] adjacencyMatrix, int NoAccess) {
		/*
		a和b的差的绝对值 <= 21
		1 与 15 符合；15-1 = 14 < 21
			这是站在1的视角
		15 与 25符合；25-15 = 10 < 21
			这是站在15的视角
			但15也与1符合
			但在内循环中我们设定j从i开始
		这里有猫腻的。我们强制设定j最小从i开始，
		是为了不让15与1	1与15这种相同的情况记录两次。
			j从i开始，每次都内循环都向前寻找abs() < 21的“新数”
			从这个角度来说，这个无向图是带环的
		 */
		for (int current = 1; current <= 2021; current++) {//按照题意生成无向图
			for (int other = current; other <= current + 21; other++) {
				adjacencyMatrix[current][other] = lcm(current, other);//对a,b相差21以内的边赋权
			}
		}
		int res = dijkstra(adjacencyMatrix, NoAccess);
		return res;
	}
	
	/**
	 * Dijkstra:按路径长度递增次序产生最短路径
		V:代表所有顶点
        bj:代表顶点是否已确定最短路径
        Dijkstra()走一遍后，其dis[]包含了“所有的源点到其他节点的最短路径”
		所以如果有需要，可以单独把dis[]摘出来返回
	 * @param adjacencyMatrix
	 * @param NoAccess
	 * @return
	 */
	public int dijkstra(int[][] adjacencyMatrix, int NoAccess) {
		boolean[] bj = new boolean[2048];//默认值是false;这个数组用来标记该点A是否找到最短路径，换一种说法就是这个数组用来标记“是否找到了从源点到此点A的最短路径”
		int[] dis = new int[2048];//用来存储“从源点开始到其他节点的尝试结果”
		int min = 0;
		int minIndex = 0;
		for (int i = 1; i <= 2021; i++) {//先把dis[]初始化成“从源点的视角，记录对其他所有节点的距离”
			dis[i] = adjacencyMatrix[1][i];
		}
		//每执行一次while循环，就确定从源点到一个新点A的最短路径
		while (!bj[2021]) {//只要结束点A还没有被标记为“找到了从源点到此点A的最短路径”
			min = Integer.MAX_VALUE;//假设一个最小值
			for (int i = 2; i <= 2021; i++) {//从源点的视角，尝试寻找一个新点A
				/*
				新点A满足：
					A没有被打上“当前图中存在从源点到A的最短路径”的标记
					在如此多的尝试中，尝试结果最短的
				 */
				if (!bj[i] && dis[i] < min) {
					min = dis[i];
					minIndex = i;
				}
			}
			/*
			 上面循环一圈以后，可以确定一个：
			 	“新的，从源点出发一直走最短路径，在已知的最短路径走完后，进行了21次尝试，
			 	在众多尝试中，某个尝试是所有尝试中，最短的，
			 	这个最短的A点”
			 	然后以A为视角，进行下面的21次尝试，直到bj[2021]==true
			 */
			bj[minIndex] = true;//A点的“从源点开始到A的最短路径”存在，其最短的数值就是min，所以打上标记；
			for (int i = minIndex + 1; i <= minIndex + 21; i++) {//开始以A为视角的21次尝试
				if (dis[i] == NoAccess) {//尝试中碰到了“本来就与源点无边相连的新点B”
//					dis[i] = dis[minIndex] + adjacencyMatrix[minIndex][i];//直接把“当前已经确定的最短路径 + ”
					dis[i] = min + adjacencyMatrix[minIndex][i];//直接把“当前已经确定的最短路径 + 无向图中A到B的距离”的值作为“尝试的结果”
				} else if (min + adjacencyMatrix[minIndex][i] < dis[i]) {//尝试中碰到“本来就与源点有边的新点B”
//					dis[i] = dis[minIndex] + adjacencyMatrix[minIndex][i];//如果“当前已经确定的最短路径 + 无向图中A到B的距离”的值足够小，小到比“尝试结果中，源点到B的距离”还小，那么就更新B点的“尝试结果”
					dis[i] = min + adjacencyMatrix[minIndex][i];//如果“当前已经确定的最短路径 + 无向图中A到B的距离”的值足够小，小到比“尝试结果中，源点到B的距离”还小，那么就更新B点的“尝试结果”
				}
			}
		}
		return dis[2021];
	}
	
	/**
	 * 最小公倍数 = a * b / gcd
	 * @param a
	 * @param b
	 * @return
	 */
	public int lcm(int a, int b) {
		return a * b / gcd(a, b);//绝对值 <= 21,有一条长度为a和b的最小公倍数的无向边相连
	}
	
	public int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}
